package com.ljy.my_study.leetcode.路径总和II;

import com.ljy.my_study.util.TreeNodeUtil;
import com.ljy.my_study.util.TreeNodeUtil.*;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lijunying
 * @date 2021/11/18 10:46
 */
public class TestMain {

//    给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
//
//    叶子节点 是指没有子节点的节点。
//
//             
//
//    示例 1：
//
//
//    输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
//    输出：[[5,4,11,2],[5,8,4,5]]
//    示例 2：
//
//
//    输入：root = [1,2,3], targetSum = 5
//    输出：[]
//    示例 3：
//
//    输入：root = [1,2], targetSum = 0
//    输出：[]
//             
//
//    提示：
//
//    树中节点总数在范围 [0, 5000] 内
//-1000 <= Node.val <= 1000
//            -1000 <= targetSum <= 1000
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/path-sum-ii
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        TreeNode root=TreeNodeUtil.deserialize("5,4,8,11,null,13,4,7,2,null,null,5,1");
        System.out.println(new TestMain().pathSum(root,22));
    }

//    dfs
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result=new ArrayList<>();
        dfs(root,0,targetSum,new ArrayList<>(),result);
        return result;
    }

    private void dfs(TreeNode root,int sum,int targetSum,List<Integer> list,List<List<Integer>> result){
        if(root==null){
            return;
        }
        int newSum=sum+root.val;
        list.add(root.val);
        if(newSum==targetSum&&root.left==null&&root.right==null){
            List<Integer> newList=new ArrayList<>(list);
            result.add(newList);
        }else{
            dfs(root.left,newSum,targetSum,list,result);
            dfs(root.right,newSum,targetSum,list,result);
        }
        list.remove(list.size()-1);
    }
}
